package alogrithm;

import java.util.ArrayList;

/**
 * @author lbw
 * @version 1.0
 * @date 2021/10/16 15:21
 */


public class PathSum {
    private final ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    private final ArrayList<Integer> path = new ArrayList<>();

    public static void main(String[] args) {
    }

    public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        // write code here
        dfs(root, 0, sum);
        return res;
    }

    private void dfs(TreeNode root, int sum, int target) {
        if (root == null) {
            return;
        }
        path.add(root.val);
        sum += root.val;
        if (root.left == null && root.right == null) {
            if (sum == target) {
                res.add(path);
            }
        } else {
            dfs(root.left, sum, target);
            dfs(root.right, sum, target);
        }
        // 将最后一个子节点删除
        sum -= path.get(path.size() - 1);
        path.remove(path.size() - 1);
    }

    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    }

}
